package _2022.hot100._70_爬楼梯;

/**
 * @author： YHSimon
 * @date： 2022-04-16 15:48
 */
public class Solution {

    //空间优化
    public int climbStairs2(int n){
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int a=1,b=2,i=3;
        while (i<=n){
            int tmp=a+b;
            a=b;
            b=tmp;
            i++;
        }
        return b;
    }
    //0ms
    public int climbStairs(int n){
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int[] res=new int[n+1];
        res[1]=1;
        res[2]=2;
        int i=3;
        while(i<=n){
            res[i]=res[i-1]+res[i-2];
            i++;
        }
        return res[n];
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.climbStairs(3));
    }
}
